package lc2;
import java.util.*;

import org.junit.Test;

public class Ex51 {
    
    class Solution {
        private List<List<String>> res;
        private int n;

        public List<List<String>> solveNQueens(int n) {
            res = new ArrayList<>();
            this.n = n;
            if (n < 1 || n > 32) {
                return res;
            }
            int limit = (1 << n) - 1;
            dfs(limit, 0, 0, 0, new int[n], 0);
            return res;
        }
        
        /**
         * limit：规定了当前皇后可以取的最大范围，用于取反后去除多余的1
         * col: 当前行皇后放置位置收到的来自列的限制
         * upLeft: 当前行皇后放置位置收到的来自左斜线的限制
         * upRight: 当前行皇后放置位置收到的来自右斜线的限制
         */
        private void dfs(int limit, int col, int upLeft, int upRight, int[] pos, int level) {
            if (col == limit) {
                //表示所有的空位都已经填满，即找到了一种有效解
                List<String> list = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    StringBuilder sb = new StringBuilder();
                    for (int j = 0; j < n; j++) {   
                        if (pos[i] == j) {
                            sb.append("Q");
                        } else {
                            sb.append(".");
                        }
                    }
                    list.add(sb.toString());
                }
                res.add(list);
                return;
            }

            // 所有的限制就是来自三方的限制求或
            int allLimit = col | upRight | upLeft;
            // 可选的位置就是在范围且没有限制的位置
            int candidates = limit & (~allLimit);

            //从右到左，依次选择一个可选位置，填充进入，并进入下一层选择
            int d = 0;
            while (candidates != 0) {
                int sub = 1 << d;
                if ((candidates & sub) != 0) {
                    //当前位置是可选位置
                    candidates -= sub;
                    pos[level] = n - d - 1;
                    dfs(
                        limit, 
                        col | sub, //列的限制增加了当前选择的这列
                        (upLeft | sub) << 1, //左斜线的限制增加了当前选择的左一位
                        (upRight | sub) >> 1, // 左斜线的限制增加了当前选择的右一位
                        pos, //用于结果获取
                        level + 1 //层数加一，作为pos下标
                    );
                }
                d++;
            }
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.solveNQueens(4));        
    }

}
